package sortingAlgorithm;

import java.util.Arrays;

//插入排序
public class InsertionSort {
    public static void main(String[] args) {
        //创建需要排序的数组对象
        int[] array = {4, 6, 9, 0, 2, 5, 3, 7, 3, 8, 3};

        //输出数组，观察原数组
        System.out.println(Arrays.toString(array));
        System.out.println();
        //从下标1的元素开始，反复对比左侧元素
        for (int i = 1; i < array.length; i++) {
            //当前需要确定位置的元素的下标，暂时假设是数组的最右侧元素
            int j = i;
            //当j>0时循环
            while (j > 0) {
                //判断j指向的元素与其左侧元素的大小
                if (array[j] < array[j - 1]) {
                    //执行换位
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    //j自减，表示想做移动
                    j--;
                    //输出数组，观察本次换位后的操作
                    System.out.println(Arrays.toString(array));
                } else {
                    //当不满足条件时(左侧元素小于或者等于右侧元素)，跳出当前循环
                    break;
                }
            }
            //输出空白行
            System.out.println();
        }
    }
}
